import java.util.HashSet;
import java.util.Set;

public class Solution945 {
    /**
     * 给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。
     *
     * 返回使 A 中的每个值都是唯一的最少操作次数。
     *
     * 示例 1:
     *
     * 输入：[1,2,2]
     * 输出：1
     * 解释：经过一次 move 操作，数组将变为 [1, 2, 3]。
     */
    //暴力
    public int minIncrementForUnique(int[] A) {
        if(A == null || A.length == 0) {
            return 0;
        }
        int result = 0;
        boolean[] set = new boolean[80000];
        for (int a : A) {
            while (set[a]){
                result ++;
                a++;
            }
            set[a] = true;
        }
        return result;
    }

    // 两次遍历
    public int minIncrementForUnique2(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        int[] status =  new int[80000];
        int counts = 0;
        for(int num : nums) {
            status[num]++;
        }
        for(int i = 0; i < 80000; i++) {
            if(status[i] > 1) {
                int expect = status[i] - 1;
                counts += expect;
                status[i + 1] += expect;
                status[i] = 1;
            }
        }
        return counts;
    }
}
